<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3488：[ONTAK2010]Highways</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[ONTAK2010]Highways</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[ONTAK2010]Highways</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [ONTAK2010]Highways                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">Byteland is a small country, with cities connected by N-1 bidirectional roads. From each city there is just one way of reaching every other city using the road network, which causes severe traffic jams. For this reason several highways have been built; each highway connects some pair of cities. <br />
By a route we mean a sequence of roads and/or highways. All cities on a route should be distinct. For each pair of cities x,y there exists exactly one route which does not use any highway; we call such a route the main route between x and y . <br />
People going from a city x to a city y can either choose the main route or use some highway. In the latter case the route cannot intersect the main route except for the cities x and&nbsp; y and must contain exactly one highway. <br />
Your task is to calculate the number of routes people can take between given pairs of cities. <br />
</span></p>
<p><span style="font-size: medium">给一棵n个点的树以及m条额外的双向边<br />
q次询问，统计满足以下条件的u到v的路径：<br />
恰经过一条额外的边<br />
不经过树上u到v的路径上的边<br />
</span></p></p><hr/><h3>输入格式</h3><p><p><br />
<font size="4">The first line of input contains a single integer N（1&lt;=N&lt;=100000） - the number of cities in Byteland. Cities are numbered from 1 to n . Each of the next N -1 lines contains two integers Ai, Bi(1&lt;=Ai,Bi&lt;=N) meaning that cities Ai and Biare connected by a road. <br />
The next line contains an integer M(1&lt;=M&lt;=100000) - the number of highways. Each of the next m lines contains a description of a single highway. The next line contains an integer Q (1&lt;=Q&lt;=500000) - the number of queries. Each of the next Q lines contains a description of a query. Both highways and queries are given in the same format as the roads. <br />
</font></p></p><hr/><h3>输出格式</h3><p><p><font size="4">Your program should output exactly Q lines. The i-th line should contain the number of routes in the i-th query. <br />
</font></p></p><hr/><h3>样例输入</h3><pre>9
1 2
2 3
4 2
1 5
5 6
7 5
7 8
9 7
4
2 5
3 4
6 4
8 3
4
4 9
2 5
1 6
1 7
</pre><hr/><h3>样例输出</h3><pre>1
4
2
2
 </pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3488" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3488" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>